#include "common.h"
namespace common {
std::vector<int> productExceptSelf(std::vector<int> &nums) {
    const int n = nums.size();
    std::vector<int> result;
    if (n == 0)
        return result;
    std::vector<int> l_prod = std::vector<int>(n, 1);
    std::vector<int> r_prod = std::vector<int>(n, 1);
    for (int l = 1; l < n; l++) {
        l_prod[l] = nums[l - 1] * l_prod[l - 1];
    }
    for (int r = n - 2; r >= 0; r--) {
        r_prod[r] = r_prod[r + 1] * nums[r + 1];
    }
    for (int i = 0; i < n; i++)
        result.push_back(l_prod[i] * r_prod[i]);
    return result;
}

std::vector<int> productExceptSelfOpt(std::vector<int> &nums) {
    const int n = nums.size();
    std::vector<int> result;
    if (n == 0)
        return result;
    result = std::vector<int>(n, 1);

    for (int l = 1; l < n; l++) {
        result[l] = nums[l - 1] * result[l - 1];
    }
    int right_prod = 1;
    for (int i = n - 1; i >= 1; i--) {
        result[i] = right_prod * result[i];
        right_prod *= nums[i];
    }
    result[0] = right_prod;
    return result;
}
} // namespace common
